// @algorithm @lc id=552 lang=cpp 
// @title student-attendance-record-ii


// #define print(...)
// @test(1)=3
// @test(2)=8
// @test(3)=19
// @test(5)=94
// @test(10100)=350160176
// @test(10101)=183236316
#define MOD 1'000'000'007
class Solution {
public:
    // Abent{0, 1}  < 2
    // Late{0, 1, 2} < 3
    // AbLa[j][k]
    int checkRecord(int n) {
        // 第1天
        int AbLa[2][3] = {
            /*Absent| Late  0    1    2 */
            {/*  0  |*/     1,   1,   0  },
            {/*  1  |*/     1,   0,   0  },
        };
        // 第 2,3, ... n 天
        for(int i=1; i<n; i++){
            int dp[2][3] = {0};
            // 追加 P
            dp[0][0] = ((long)AbLa[0][0] + AbLa[0][1] + AbLa[0][2])%MOD;
            dp[1][0] = ((long)AbLa[1][0] + AbLa[1][1] + AbLa[1][2])%MOD;
            // 追加 A
            dp[1][0] = ((long)AbLa[0][0] + AbLa[0][1] + AbLa[0][2] + dp[1][0])%MOD;
            // 追加 L
            dp[0][1] = AbLa[0][0];
            dp[0][2] = AbLa[0][1];
            dp[1][1] = AbLa[1][0];
            dp[1][2] = AbLa[1][1];
            memcpy(AbLa, dp, sizeof(dp));
        }
        int ans = 0;
        for(int j=0; j<2; j++)
            for(int k=0; k<3; k++)
                ans = ((long)AbLa[j][k] + ans)%MOD;
        return ans;
    }
};